package com.origin.niuke.bit_operation;

import java.util.Arrays;

/**
 * NC75 数组中只出现一次的两个数字
 * 算法：位运算
 * 将数组异或, 可以找到数组中两个不同数的异或结果
 * 通过两个数的异或结果, 可以找到这两个数从右到左第 n 个位上数字不同的情况
 * 通过 n 将数组分成两个部分, 一部分的数的第 n 位为 0, 另一部分的数的第 n 位为 1
 *
 * @author yezh
 * @date 2022/11/17 9:04
 */
public class NC75 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new NC75().FindNumsAppearOnce(new int[]{1, 4, 3, 3, 4, 5,})));
    }

    public int[] FindNumsAppearOnce(int[] array) {
        int xor = 0, a = 0, b = 0, mask = 1;
        for (int num : array) xor ^= num;
        while ((xor & mask) == 0) mask <<= 1;
        for (int num : array) {
            if ((num & mask) == 0) a ^= num;
            else b ^= num;
        }
        int[] ans = new int[2];
        if (a < b) {
            ans[0] = a;
            ans[1] = b;
        } else {
            ans[0] = b;
            ans[1] = a;
        }
        return ans;
    }

}
